<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>shortest_path</title>
  </head>
  <body bgcolor="#FFFFFF">
    <center>Scilab function</center>
    <div align="right">Last update : 16/12/2005</div>
    <p>
      <b>shortest_path</b> - shortest path</p>
    <h3>
      <font color="blue">Calling Sequence</font>
    </h3>
    <dl>
      <dd>
        <tt>[p,lp] =
    shortest_path(i,j,g,[typ])</tt>
      </dd>
    </dl>
    <h3>
      <font color="blue">Parameters</font>
    </h3>
    <ul>
      <li>
        <tt>
          <b>i</b>
        </tt>: integer, number of start node</li>
      <li>
        <tt>
          <b>j</b>
        </tt>: integer, number of end node</li>
      <li>
        <tt>
          <b>g</b>
        </tt>: graph list</li>
      <li>
        <tt>
          <b>typ</b>
        </tt>: string, type of shortest path</li>
      <li>
        <tt>
          <b>p</b>
        </tt>: row vector of integer numbers of the arcs of the shortest path
          if it exists</li>
      <li>
        <tt>
          <b>lp</b>
        </tt>: length of shortest path</li>
    </ul>
    <h3>
      <font color="blue">Description</font>
    </h3>
    <p>
      <tt>
        <b>shortest_path</b>
      </tt> returns the shortest path <tt>
        <b>p</b>
      </tt>
    from node <tt>
        <b>i</b>
      </tt> to node <tt>
        <b>j</b>
      </tt> if it exists, and the
    empty vector <tt>
        <b>[]</b>
      </tt> otherwise. The optional argument
    <tt>
        <b>typ</b>
      </tt> is a string which defines the type of shortest path,
    'arc' for the shortest path with respect to the number of arcs and
    'length' for the shortest path with respect to the length of the edges
    <tt>
        <b>edge_length</b>
      </tt>.</p>
    <p>For the shortest path with respect to the length of the edges, the
    lengths are given by the element <tt>
        <b>edge_length</b>
      </tt> of the graph
    list. If its value is not given (empty vector <tt>
        <b>[]</b>
      </tt>), it is
    assumed to be equal to 0 on each edge. Lengths can be positive, equal to 0
    or negative.</p>
    <p>When a shortest path exists, <tt>
        <b>lp</b>
      </tt> is the length of this
    path.</p>
    <h3>
      <font color="blue">Examples</font>
    </h3>
    <pre>

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548]; 
g('node_y')=[56 181 276 278 276 103 174 281 177 86 175 90 290 397 399];
show_graph(g);
g1=g;ma=prod(size(g1('head')));
rand('uniform');
g1('edge_length')=int(20*rand(1,ma));
[p,lp]=shortest_path(13,1,g1,'length');
p
x_message(['Showing the arcs of the shortest path ';
           'Arcs names can be displayed by selecting the value ""Name"" for arcs in the Graph-&gt;Options menu.']);
g1('edge_name')=string(g1('edge_length'));
edgecolor=ones(1:ma);edgecolor(p)=11*ones(p);
g1('edge_color')=edgecolor;
edgefontsize=12*ones(1,ma);edgefontsize(p)=18*ones(p);
g1('edge_font_size')=edgefontsize;
show_graph(g1);
 
  </pre>
    <h3>
      <font color="blue">See Also</font>
    </h3>
    <p>
      <a href="find_path.htm">
        <tt>
          <b>find_path</b>
        </tt>
      </a>,&nbsp;&nbsp;<a href="nodes_2_path.htm">
        <tt>
          <b>nodes_2_path</b>
        </tt>
      </a>,&nbsp;&nbsp;</p>
  </body>
</html>
